Grupowanie hierarchiczne

Grupowanie hierarchiczne, hierarchiczna analiza skupień, klasteryzacja hierarchiczna, klastrowanie hierarchiczne – w eksploracji danych i statystyce: metoda analizy skupień, która ma na celu zbudowanie hierarchii klastrów. Służy do dzielenia obserwacji na grupy (klastry) bazując na podobieństwach między nimi. W przeciwieństwie do wielu algorytmów służących do klastrowania w tym wypadku nie jest konieczne wstępne określenie liczby tworzonych klastrów^[1]. Strategie tworzenia klastrów hierarchicznych dzielą się zasadniczo na dwa typy^[2]:

metody aglomeracyjne (ang. agglomerative) – każda obserwacja tworzy na początku jednoelementowy klaster. Następnie pary klastrów są scalane, w każdej iteracji algorytmu łączone są z sobą dwa najbardziej zbliżone klastry. Tworzone są tak zwane aglomeracje. W tym typie podczas tworzenia klastrów idzie się w górę hierarchii.
metody deglomeracyjne (ang. divisive) – początkowo wszystkie obserwacje znajdują się w jednym klastrze. W następnych krokach klastry dzielone są na mniejsze i bardziej jednorodne. Podziały wykonywane są rekursywnie. W czasie tworzenia klastrów idzie się w dół hierarchii.

Algorytmy grupowania hierarchicznego charakteryzują się złożonością obliczeniową O(n³) oraz wymagają O(n²) pamięci, co czyni je mało efektywnymi. Wyniki hierarchicznego grupowania stanowią zestaw zagnieżdżonych klastrów, które są zwykle prezentowane w dendrogramie. Dendrogram jest wielopoziomową hierarchią, w której klastry z jednego poziomu są połączone i tworzą większe klastry na kolejnych poziomach. Umożliwia on określenie poziomu, na który należy wyciąć drzewo w celu wygenerowania odpowiedniej ilości klastrów.

Stosując algorytmy grupowania hierarchicznego, konieczne jest dokonanie pomiaru odległości między punktami. Głównym celem jest to, aby odległości między obserwacjami tego samego klastra były możliwie jak najmniejsze, natomiast odległości między klastrami były jak największe. W hierarchicznym grupowaniu istnieją dwa bardzo ważne parametry: metryka odległości i metoda połączenia.

↑ Alboukadel Kassambara: Practical Guide To Cluster Analysis in R. STHDA, 2017.
↑ Rokach, Lior, and Oded Maimon: „Clustering methods.” Data mining and knowledge discovery handbook. Springer, 2005, s. 321–352.

[autonazwa1-1] Alboukadel Kassambara: Practical Guide To Cluster Analysis in R. STHDA, 2017.

[2] Rokach, Lior, and Oded Maimon: „Clustering methods.” Data mining and knowledge discovery handbook. Springer, 2005, s. 321–352.

[1]

[2]